#include "Train.h"

class Solution {
public:
   int shortestSubarray(vector<int>& nums, int k) {
       int n = nums.size();
       vector<long long> s(n + 1, 0);//前缀和数组
       for (int i = 1; i <= n; i++) {
           s[i] = s[i - 1] + nums[i - 1];
       }
       deque<int>q;
       q.push_back(0);
       int ans = n + 1;
       for (int i = 1; i <= n; i++) {
           while (!q.empty() && s[i] - s[q.front()] >= k) {
               ans = min(ans, i - q.front());
               q.pop_front();
           }

           while (!q.empty() && s[i] < s[q.back()]) q.pop_back();
           q.push_back(i);
       }

       if (ans == n + 1) return -1;
       return ans;
   }
};